package com.algorithm.string;

import java.util.Arrays;

/**
 * 模式匹配之BM匹配
 */
public class PatternMatchBM {

    public static void main(String[] args) {
        //int[] table = makeCharTable("abcdef");
        String pattern = "abcdef";
        int[] table = makeOffsetTable(pattern);
        System.out.println(Arrays.toString(table));
        int match = patternMatch("abcabcdabcdef", pattern);
        System.out.println(match);
    }

    /**
     * Boyer-Moore
     * @author DBJ
     */
    /**
     * 这个算法由Bob Boyer和J Strother Moore设计于1977年。
     *
     * @param target  目标串
     * @param pattern 模式串
     * @return 模式串在目标串中第一次出现的位置
     */
    public static int patternMatch(String target, String pattern) {
        int targetLength = target.length();
        int patternLength = pattern.length();

        if (patternLength == 0) {
            return 0;
        }

        int[] charTable = makeCharTable(pattern);
        int[] offsetTable = makeOffsetTable(pattern);

        for (int i = patternLength - 1, j; i < targetLength; ) {
            for (j = patternLength - 1; pattern.charAt(j) == target.charAt(i); --i, --j) {
                if (j == 0) {
                    return i;
                }
            }
            // 模式串移动距离为 坏字符规则和好后缀规则中最大的那个即可
            int offsetGoodSuffix = offsetTable[patternLength - 1 - j];
            i += Math.max(offsetGoodSuffix, charTable[target.charAt(i)]);
        }
        return -1;
    }

    /**
     * 创建不匹配的字符信息表。坏字符移动距离
     * 目的:记录当遇到坏字符时模式串前移的距离
     * 如果模式串中不存在该坏字符,则直接移动到坏字符下一位即可
     *  如果存在,则需要移动到坏字符出现的最右侧位置(重复出现的坏字符从0...i循环时会被最右侧覆盖,刚好符合要求)
     * @param pattern 模式串
     * @return
     */
    private static int[] makeCharTable(String pattern) {
        final int ALPHABET_SIZE = 256;
        int[] table = new int[ALPHABET_SIZE];
        int patternLength = pattern.length();

        for (int i = 0; i < table.length; ++i) {
            table[i] = patternLength;
        }
        for (int i = 0; i < patternLength - 1; ++i) {
            table[pattern.charAt(i)] = patternLength - 1 - i;
        }
        return table;
    }

    /**
     * 创建不匹配时扫描偏移量表。
     * 好后缀规则:
     *     前提:模式串中可能出现相似子串,重复扫描浪费性能
     *     对于字符串如str = abcdeabdfabc来说,好后缀为abc,因为好后缀必须以str[0] 开头,直到结尾都与str开头部分一致.
     *     如其间的abdf子串是不合法的,因为到d的时候与前缀abc第三位c已经不一致了,移动到这里肯定还要继续后移才行
     * @param pattern 模式串
     * @return
     */
    private static int[] makeOffsetTable(String pattern) {
        int patternLength = pattern.length();
        int[] table = new int[patternLength];
        int lastPrefixPosition = patternLength;

        for (int i = patternLength - 1; i >= 0; --i) {
            // 判断是否是好后缀(=前缀)
            if (isPrefix(pattern, i + 1)) {
                lastPrefixPosition = i + 1;
            }
            /**
             * 如果是
             *
             */
            table[patternLength - 1 - i] = lastPrefixPosition - i + patternLength - 1;
        }

        for (int i = 0; i < patternLength - 1; ++i) {
            int slen = suffixLength(pattern, i);
            table[slen] = patternLength - 1 - i + slen;
        }
        return table;
    }

    /**
     * isPrefix
     *
     * @param pattern 模式串
     * @param p       起始
     * @return
     */
    private static boolean isPrefix(String pattern, int p) {
        int patternLength = pattern.length();
        for (int i = p, j = 0; i < patternLength; ++i, ++j) {
            if (pattern.charAt(i) != pattern.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 后缀。
     *
     * @param pattern 模式串
     * @param p       起始
     * @return
     */
    private static int suffixLength(String pattern, int p) {
        int patternLength = pattern.length();
        int len = 0;
        for (int i = p, j = patternLength - 1; i >= 0 && pattern.charAt(i) == pattern.charAt(j); --i, --j) {
            len += 1;
        }
        return len;
    }
}
